//
// Created by ASUS on 2024/7/3/星期三.
//
/*
给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：
首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。
示例 1：
输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
示例 3：
输入：s = "leetcode", k = 8
输出：0
提示：
1 <= k <= s.length <= 100
s 中只含有小写英文字母。
*/
#include <bits/stdc++.h>
using namespace std;

int palindromePartition(string s, int k) {
	int n = s.length();
	vector<vector<int>> f(k+1, vector<int>(n + 1,INT_MAX/2)); // f[i][j]代表s[0:j)分割成i段需要更改的数字
	f[0][0]=0;
	vector<vector<int>> g(n, vector<int>(n, 0)); // g[i][j]->s[i:j]变成回文串需要修改的字符数
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			g[i][j] = (s[i] != s[j]) + g[i + 1][j - 1];
		}
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int L = j - 1; L >= 0; L--) {
				f[i][j] = min(f[i][j] , f[i-1][L]+g[L][j-1]);
			}
		}
	}
	return f[k][n];
}
//滚动数组优化
int palindromePartition1(string s, int k) {
	int n = s.length();
	vector<int> f(n + 1,INT_MAX/2); // f[j]代表s[0:j)分割成i段需要更改的数字
	f[0]=0;
	vector<vector<int>> cost(n, vector<int>(n, 0)); // cost[i][j]->s[i:j]变成回文串需要修改的字符数
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
		}
	}
	for (int i = 1; i <= k; i++) {
		vector<int> g(n+1,INT_MAX/2);
		for (int j = 1; j <= n; j++) {
			for (int L = j - 1; L >= 0; L--) {
				g[j] = min(g[j] , f[L]+cost[L][j-1]);
			}
		}
		f=move(g);
	}
	return f[n];
}
//O(n^2k)